package org.kgduyjj.toolbox.algorithms;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.Random;
import java.util.TreeMap;

import org.kgduyjj.toolbox.bean.DefaultAward;
import org.kgduyjj.toolbox.exception.AlgorithmsException;

public class LotteryMethod {
    /** 完全概率，权重为1，概率为100% **/
    private static final double FULL_PROBABILITY = 1;
    /** 补充奖项最大数量 10万 **/
    private static final int UNLUCK_AWARD_MAX_QUOTA = 100000;
    /** 随机对象 **/
    private static Random random;
    /** 别名数组 **/
    private static int[] alias;
    /** 概率数组 **/
    private static double[] probability;

    /**
     * 构造器 使用默认的随机工具
     * 
     * @param probabilities 概率池
     */
    private LotteryMethod(List<Double> probabilities) {
        this(probabilities, new Random());
    }

    /**
     * 构造器
     * 
     * @param probabilities 概率池
     * @param random        随机工具
     */
    private LotteryMethod(List<Double> probabilities, Random cfgRandom) {
        if (probabilities == null || cfgRandom == null) {
            throw new AlgorithmsException("Probabilities or alias method gen is null.");
        }
        if (probabilities.size() == 0) {
            throw new AlgorithmsException("Probability vector must be nonempty.");
        }
        random = cfgRandom;
        initAliasMethod(probabilities);
    }

    /**
     * 抽奖算法 <br/>
     * 使用Alias Method 算法预处理抽奖概率
     * 
     * @param probabilities
     */
    private void initAliasMethod(List<Double> probabilities) {
        probability = new double[probabilities.size()];
        alias = new int[probabilities.size()];
        final double average = 1.0 / probabilities.size();
        probabilities = new ArrayList<Double>(probabilities);
        Deque<Integer> small = new ArrayDeque<Integer>();
        Deque<Integer> large = new ArrayDeque<Integer>();
        for (int i = 0; i < probabilities.size(); ++i) {
            if (probabilities.get(i) >= average)
                large.add(i);
            else
                small.add(i);
        }
        while (!small.isEmpty() && !large.isEmpty()) {
            int less = small.removeLast();
            int more = large.removeLast();
            probability[less] = probabilities.get(less) * probabilities.size();
            alias[less] = more;
            probabilities.set(more, (probabilities.get(more) + probabilities.get(less)) - average);
            if (probabilities.get(more) >= 1.0 / probabilities.size())
                large.add(more);
            else
                small.add(more);
        }
        while (!small.isEmpty())
            probability[small.removeLast()] = 1.0;
        while (!large.isEmpty())
            probability[large.removeLast()] = 1.0;
    }

    /**
     * 抽选别名下标位置
     * 
     * @return
     */
    private int next() {
        int column = random.nextInt(probability.length);
        boolean coinToss = random.nextDouble() < probability[column];
        return coinToss ? column : alias[column];
    }

    /**
     * 抽奖转盘
     * 
     * @param prizePool 奖品池 保证奖品类重写了hashCode方法和实现了Comparable接口
     * @return
     */
    public static <T extends DefaultAward> T lottery(List<T> pool) {
        TreeMap<T, Double> map = new TreeMap<T, Double>();
        for (T award : pool) {
            map.put(award, award.getProbability());
        }
        // 将所有奖品抽选概率放入备选队列中
        List<Double> probabilities = new ArrayList<Double>(map.values());
        // 生成抽奖算法工具
        LotteryMethod method = new LotteryMethod(probabilities);
        // 抽选奖品
        return pool.get(method.next());
    }

    /**
     * 补充非参与计算的奖项
     * 
     * @param <T>
     * 
     * @param prizePool
     * @param unluckPrizeName
     * @return
     */
    @SuppressWarnings("unchecked")
    public static <T extends DefaultAward> List<T> supTempAward(List<T> pool, T... tempAwards) {
        if (null == tempAwards || tempAwards.length == 0) {
            // 无效的未中奖奖项
            throw new AlgorithmsException("Invalid not winning the award.");
        }
        double factTotalProbability = 0D, tempProbability = 0D;
        for (T award : pool) {
            factTotalProbability += award.getProbability();
        }
        int tempQty = tempAwards.length;
        tempProbability = FULL_PROBABILITY - factTotalProbability;// 未中奖概率

        double singleTempProbability = tempProbability / tempQty;
        for (T tempAward : tempAwards) {
            tempAward.setProbability(singleTempProbability);
            tempAward.setCurrentQuota(UNLUCK_AWARD_MAX_QUOTA);
            pool.add(tempAward);
        }
        return pool;
    }

    /**
     * 计算非中奖项中奖概率，与{@link #supTempAward(List, Award...)}方法类似，但返回的是非中奖项计算概率后的集合
     * 
     * @param prizePool
     * @param temp
     * @return
     */
    @SuppressWarnings("unchecked")
    public static <T extends DefaultAward> List<T> obtainAndCalculateTempAward(List<T> pool, T... tempAwards) {
        if (null == tempAwards || tempAwards.length == 0) {
            return null;
        }
        double luckProbability = 0D, tempProbability = 0D;
        for (T award : pool) {
            luckProbability += award.getProbability();
        }
        int tempQty = tempAwards.length;
        List<T> tempPool = new ArrayList<T>(tempQty);
        tempProbability = FULL_PROBABILITY - luckProbability;// 未中奖概率
        double singleTempProbability = tempProbability / tempQty;
        for (T tempAward : tempAwards) {
            tempAward.setProbability(singleTempProbability);
            tempAward.setCurrentQuota(UNLUCK_AWARD_MAX_QUOTA);
            tempPool.add(tempAward);
        }
        return tempPool;
    }

}
